PGCD et congruence - Corrigé

Énoncé

Soit \(n\) un entier naturel tel que \(n>4\) . On pose \(a=2n+13\) et \(b=n+3\) .

1. Écrire la division euclidienne de \(a\) par \(b\) .

2. En déduire que \(\mathrm{PGCD}(a;b)\) divise \(7\) .

3. Montrer que : \(\mathrm{PGCD}(a;b)=7 \ \Longleftrightarrow \ n \equiv 4 \ [7]\) .

Solution

1. On a : \(2n+13=(n+3) \times 2+7\) avec \(0 \leqslant 7 < n+3\) car \(n>4\) .

2. D'après le lemme d'Euclide, \(\mathrm{PGCD}(a;b)=\mathrm{PGCD}(2n+13;n+3)=\mathrm{PGCD}(n+3;7)\) .
Or \(\mathrm{PGCD}(n+3;7)\) est un diviseur de \(7\) , donc \(\mathrm{PGCD}(a;b)\) divise \(7\) .

3. On a :
\(\begin{align*} \mathrm{PGCD}(a;b)=7 & \ \ \Longleftrightarrow \ \ \mathrm{PGCD}(n+3;7)=7 \\&\ \ \Longleftrightarrow \ \ 7 \text{ divise } n+3 \\ & \ \ \Longleftrightarrow \ \ n+3 \equiv 0 \ [7] \\ & \ \ \Longleftrightarrow \ \ n \equiv -3 \equiv 4 \ [4] \end{align*}\)